# coding: utf-8
from typing import List


class Solution:
    # 拓扑排序
    # prerequisites里面的每个都是一个二元组 [a,b]--> 表示a是b的先行课程
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        S = [0 for i in range(numCourses)]
        L = []
        for pre_course in prerequisites:
            # 表示该课程有先行课，且数值为先行课的数量
            S[pre_course[1]] = S[pre_course[1]] + 1

        left = numCourses

        for i in range(numCourses):
            if S[i] == 0:
                left = left-1
                L.append(i)
                # 需要删除以该节点为先行课的边
                for pre_courese in prerequisites:
                    if pre_courese[0] == i:
                        if pre_courese[1] in L:
                            # 出现环
                            return False
                        S[pre_courese[1]] = S[pre_courese[1]] - 1
                S[i] = -1 # 表示该课程已经不在S中了

        while left > 0:
            flag = True
            for i in range(numCourses):
                if S[i] == 0:
                    flag = False
                    left = left - 1
                    L.append(i)
                    S[i] = -1 # 表示该课程已经不在S中了
                    # 需要删除以该节点为先行课的边
                    for pre_courese in prerequisites:
                        if pre_courese[0] == i:
                            if pre_courese[1] in L:
                                return False
                            S[pre_courese[1]] = S[pre_courese[1]] - 1
            if flag:
                return False

        if left == 0:
            return True
        else:
            return False
       

if __name__ == '__main__':
    solu = Solution()
    # print(solu.maximumDifference([1, 5, 2, 10]))
    print(solu.canFinish(20,[[0,10],[3,18],[5,5],[6,11],[11,14],[13,1],[15,1],[17,4]]))
